{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures - Circular Linked Lists\n",
    "\n",
    "A circular linked list is a sequence of individual data elements called Nodes, which are connected via links. Each data element contains a connection to another data element in the form of a pointer. Visually we can think of a node like the following:\n",
    "\n",
    "<img src=\"LinkedLists - Node.png\" width=\"200\">\n",
    "\n",
    "A collection of nodes is called a list, and can be visualized as the following:\n",
    "\n",
    "<img src=\"CircularLinkedList - List.png\" width=\"300\">\n",
    "\n",
    "A circular linked lists differs from a singly linked list because instead of the last node pointing to a `null` value, it instead points back to the head node.\n",
    "\n",
    "### Advantages\n",
    "\n",
    "1. Entire list can be traversed from any node.\n",
    "2. Circular lists are the required data structure when we want a list to be accessed in a circle or loop.\n",
    "3. Despite of being singly circular linked list we can easily traverse to its previous node, which is not possible in singly linked list.\n",
    "\n",
    "### Disadvantages\n",
    "\n",
    "1. Circular list are complex as compared to singly linked lists.\n",
    "2. Reversing of circular list is a complex as compared to singly or doubly lists.\n",
    "3. If not traversed carefully, then we could end up in an infinite loop.\n",
    "4. Like singly and doubly lists circular linked lists also doesn’t supports direct accessing of elements.\n",
    "\n",
    "### Why Use Circular Linked Lists\n",
    "\n",
    "- Circular lists are used in applications where the entire list is accessed one-by-one in a loop. Example: Operating systems may use it to switch between various running applications in a circular loop.\n",
    "- It is also used by Operating system to share time for different users, generally uses Round-Robin time sharing mechanism.\n",
    "- Multiplayer games uses circular list to swap between players in a loop.\n",
    "\n",
    "\n",
    "### Performance\n",
    "\n",
    "| Data Structure | Average Insert | Average Delete | Average Search | Worst Insert | Worst Delete | Worst Search |\n",
    "|----------------|----------------|----------------|----------------|--------------|--------------|--------------|\n",
    "| Circular Linked List    | O(1)           | O(1)           | O(n)           | O(1)         | O(1)         | O(n)         |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self, data = None, next_node = None):\n",
    "        self.data = data\n",
    "        self.next_node = next_node\n",
    "        \n",
    "        \n",
    "class CircularLinkedList(object):\n",
    "    \n",
    "    def __init__(self, head = None, end = None):\n",
    "        '''\n",
    "            Initalize a linke list with a head and a tail.\n",
    "        '''\n",
    "        \n",
    "        self.head = head\n",
    "        self.end = end\n",
    "        \n",
    "    def traverse(self):\n",
    "        '''\n",
    "            Traverse the list and print each value.\n",
    "            Time Complexity: O(n)\n",
    "        '''\n",
    "        \n",
    "        # define the first node\n",
    "        curr_node = self.head\n",
    "        \n",
    "        # as long as there is a next node, keep going\n",
    "        while curr_node.next_node:\n",
    "            \n",
    "            # print the data\n",
    "            print(curr_node.data)\n",
    "            \n",
    "            # reassign the next node\n",
    "            curr_node = curr_node.next_node\n",
    "            \n",
    "            # here is the issue, if we don't add this condition we get an ifinite loop.\n",
    "            # Once the current node is the head again, then exit the loop.\n",
    "            if curr_node == self.head:\n",
    "                break\n",
    "        \n",
    "        \n",
    "    def insert_end(self, data):\n",
    "        '''\n",
    "            Insert a node at the end of our linked list.\n",
    "            Time Complexity: O(1)\n",
    "        '''  \n",
    "        \n",
    "        new_node = Node(data) \n",
    "        \n",
    "        # handle empty list case\n",
    "        if self.head == None:            \n",
    "            self.head = new_node\n",
    "            self.head.next_node = new_node\n",
    "            self.end = new_node\n",
    "            return\n",
    "        \n",
    "        # handle non-empty list case\n",
    "        if self.end != None:\n",
    "            self.end.next_node = new_node\n",
    "            new_node.next_node = self.head        \n",
    "            self.end = new_node\n",
    "            return\n",
    "                \n",
    "            \n",
    "    def insert_beg(self, data):\n",
    "        '''\n",
    "            Insert a node at the beginning of our linked list.\n",
    "            Time Complexity: O(1)\n",
    "        ''' \n",
    "        \n",
    "        new_node = Node(data)\n",
    "        new_node.next_node = self.head        \n",
    "        curr_node = self.head\n",
    "                   \n",
    "        # handle empty list case\n",
    "        if curr_node == None:            \n",
    "            self.head = new_node\n",
    "            self.end = new_node\n",
    "            self.head.next_node = new_node\n",
    "            return\n",
    "        \n",
    "        # handle non-empty list case\n",
    "        if self.end != None:\n",
    "            self.end.next_node = new_node\n",
    "            new_node.next_node = self.head        \n",
    "            self.head = new_node\n",
    "            return\n",
    "        \n",
    "        \n",
    "    def insert_mid(self, ref_node, data):\n",
    "        '''\n",
    "            Insert a node at the middle of our linked list, after a given node.\n",
    "            Time Complexity: O(1)\n",
    "        ''' \n",
    "        \n",
    "        # handle empty node case\n",
    "        if ref_node == None:\n",
    "            print(\"You've selected an empty node.\")\n",
    "            \n",
    "        # if we are inserting after the end node, then just use the insert_end method\n",
    "        if ref_node == self.end:\n",
    "            self.insert_end(data)\n",
    "            return\n",
    "        \n",
    "        # otherwise it's a true mid.\n",
    "        new_node = Node(data)            \n",
    "        ref_next = ref_node.next_node        \n",
    "        ref_node.next_node = new_node\n",
    "        new_node.next_node = ref_next\n",
    "        \n",
    "    \n",
    "    def delete_beg(self):\n",
    "        '''\n",
    "            Delete a node at the beginning of our list.\n",
    "            Time Complexity: O(1)\n",
    "        ''' \n",
    "        \n",
    "        if self.head != None:\n",
    "            \n",
    "            # grab the node that comes after the head.\n",
    "            aft_head = self.head.next_node\n",
    "            \n",
    "            # have the last node now point to that node\n",
    "            self.end.next_node = aft_head\n",
    "            \n",
    "            # set the head property.\n",
    "            self.head = aft_head\n",
    "            \n",
    "        else:\n",
    "            raise ValueError(\"The list is empty\")\n",
    "          \n",
    "        \n",
    "    def delete_end(self):\n",
    "        '''\n",
    "            Delete a node at the end of our list.\n",
    "            Time Complexity: O(1)\n",
    "        ''' \n",
    "        \n",
    "        if self.end != None:\n",
    "            \n",
    "            # grab the head\n",
    "            curr_node = self.head\n",
    "            \n",
    "            # traverse until the end\n",
    "            while curr_node.next_node.next_node != self.head:                        \n",
    "                curr_node = curr_node.next_node\n",
    "             \n",
    "            # set the last node equal to the node before the last one.\n",
    "            self.end = curr_node\n",
    "            \n",
    "            # have the new last node link to the head.\n",
    "            curr_node.next_node = self.head\n",
    "            \n",
    "        else:\n",
    "            raise ValueError(\"The list is empty\")\n",
    "            \n",
    "            \n",
    "    def delete_mid(self, position):\n",
    "        '''\n",
    "            Delete a node in the middle of our list, after that given node.\n",
    "            Time Complexity: O(n)\n",
    "        ''' \n",
    "        \n",
    "        # if position is 0 then delete first.\n",
    "        if position == 0:            \n",
    "            self.delete_beg()\n",
    "            return\n",
    "        \n",
    "        # if position is the size of the list then delete the last one.\n",
    "        if position == self.list_size():\n",
    "            self.delete_end()\n",
    "            return\n",
    "        \n",
    "        # grab the node after the head.\n",
    "        curr_node = self.head.next_node\n",
    "        \n",
    "        # initalize count\n",
    "        count = 0\n",
    "        \n",
    "        # traverse till you reach the position\n",
    "        while count <= position:            \n",
    "            count = count + 1 \n",
    "            curr_node = curr_node.next_node\n",
    "            \n",
    "        # have it point to the node after the one you want to delete.\n",
    "        curr_node.next_node = curr_node.next_node.next_node\n",
    "        \n",
    "            \n",
    "    def list_size(self):\n",
    "        '''\n",
    "            Return the size of our list.\n",
    "            Time Complexity: O(n)\n",
    "        ''' \n",
    "        \n",
    "        # grab the head\n",
    "        curr_node = self.head\n",
    "        count = 0\n",
    "        \n",
    "        # traver until you reach the head again\n",
    "        while curr_node.next_node:\n",
    "            \n",
    "            count = count + 1            \n",
    "            curr_node = curr_node.next_node\n",
    "            \n",
    "            # prevents infinite loop\n",
    "            if curr_node == self.head:\n",
    "                break\n",
    "                \n",
    "        return count\n",
    "    \n",
    "    \n",
    "    def get_prev_node(self, ref_node):\n",
    "        '''\n",
    "            Return the node before a given reference node.\n",
    "            Time Complexity: O(n)\n",
    "        ''' \n",
    "        \n",
    "        # handle empty list case\n",
    "        if self.head is None:\n",
    "            raise ValueError(\"The list is empty\")\n",
    "        \n",
    "        # define the first node\n",
    "        current = self.head\n",
    "        \n",
    "        # keep going until you reach the desired node.\n",
    "        while current.next_node != ref_node:\n",
    "            current = current.next_node\n",
    "                   \n",
    "        return current\n",
    "       \n",
    "        \n",
    "    def reverse(self):\n",
    "        '''\n",
    "            Reverse the circular list, so that the tail is now the head.\n",
    "            Time Complexity: O(n)\n",
    "        ''' \n",
    "        \n",
    "        # if the head is empty return\n",
    "        if self.head is None:\n",
    "            raise ValueError(\"The list is empty\")\n",
    "        \n",
    "        # initalize a few of our variables\n",
    "        last = self.head\n",
    "        curr = self.head\n",
    "        prev = self.end        \n",
    "        next = curr.next_node\n",
    "        \n",
    "        # reassign the last node to the head's next node\n",
    "        curr.next_node = prev \n",
    "        \n",
    "        # the old previous now becomes the old current\n",
    "        prev = curr\n",
    "        \n",
    "        # the old current now becomes the old next, the one after the head\n",
    "        curr = next\n",
    "        \n",
    "        # keep going until you reach the last node\n",
    "        while curr != last:\n",
    "            \n",
    "            # reassign next\n",
    "            next=curr.next_node\n",
    "            \n",
    "            # do the same reassignment steps as upabove\n",
    "            curr.next_node = prev\n",
    "            prev = curr\n",
    "            curr = next\n",
    "        \n",
    "        # one final reassignment, make sure the last node points to the head\n",
    "        curr.next_node = prev\n",
    "        \n",
    "        # then redefine your head and tail.\n",
    "        self.head = prev\n",
    "        self.end = curr\n",
    "      \n",
    "    \n",
    "    def split_list(self, head1, head2):\n",
    "        '''            \n",
    "            Split the list into two separate circular linked list.\n",
    "            Time Complexity: O(n)\n",
    "            \n",
    "            PARA: head1\n",
    "            TYPE: CircularLinkedList\n",
    "            \n",
    "            PARA: head2\n",
    "            TYPE: CircularLinkedList\n",
    "        ''' \n",
    "        \n",
    "        slow_ptr = self.head\n",
    "        fast_ptr = self.head\n",
    "        \n",
    "        # handle empty list case\n",
    "        if self.head is None:\n",
    "            raise ValueError(\"The list is empty\")\n",
    "        \n",
    "        # For ODD NODES: fast_ptr.next_node will become the head.\n",
    "        # For EVEN NODES: fast_ptr.next_node.next_node will become the head.\n",
    "        while (fast_ptr.next_node != self.head and fast_ptr.next_node.next_node != self.head):\n",
    "            fast_ptr = fast_ptr.next_node.next_node\n",
    "            slow_ptr = slow_ptr.next_node\n",
    "        \n",
    "        # if the fast pointer next next is the head, just stop one node before to get the last element of our list.\n",
    "        if fast_ptr.next_node.next_node == self.head:\n",
    "            fast_ptr = fast_ptr.next_node\n",
    "        \n",
    "        # Set the head pointer of first half \n",
    "        head1.head = self.head\n",
    "        \n",
    "        # Set the head pointer of second half \n",
    "        if self.head.next_node != self.head:\n",
    "            head2.head = slow_ptr.next_node\n",
    "        \n",
    "        # Make second half circular \n",
    "        fast_ptr.next_node = slow_ptr.next_node\n",
    "        \n",
    "        # Make first half circular\n",
    "        slow_ptr.next_node = self.head\n",
    "        \n",
    "    def split_list_2(self, head1, head2):\n",
    "        '''            \n",
    "            Split the list into two separate circular linked list.\n",
    "            Time Complexity: O(n)\n",
    "            \n",
    "            PARA: head1\n",
    "            TYPE: CircularLinkedList\n",
    "            \n",
    "            PARA: head2\n",
    "            TYPE: CircularLinkedList\n",
    "        ''' \n",
    "        \n",
    "        # grab the list size\n",
    "        list_size = self.list_size()\n",
    "        \n",
    "        # grab the midpoint\n",
    "        mid = list_size // 2\n",
    "   \n",
    "        # get the first node\n",
    "        curr = self.head\n",
    "        \n",
    "        # go while the count is less than the list size\n",
    "        count = 0        \n",
    "        while count <= list_size - 1:\n",
    "            \n",
    "            # grab the data\n",
    "            data = curr.data\n",
    "            \n",
    "            # if it's less than the mid, put in list one\n",
    "            if count < mid:\n",
    "                head1.insert_beg(data)\n",
    "            \n",
    "            # if it's greater than the mid, put it in list two\n",
    "            if count >= mid:\n",
    "                head2.insert_beg(data)\n",
    "                \n",
    "            # grab the next node.\n",
    "            curr = curr.next_node\n",
    "            \n",
    "            # increment the counter\n",
    "            count = count + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After Insertion\n",
      "--------------------\n",
      "100\n",
      "90\n",
      "50\n",
      "60\n",
      "70\n",
      "After Mid Insertion\n",
      "--------------------\n",
      "100\n",
      "90\n",
      "50\n",
      "60\n",
      "70\n",
      "20\n",
      "Before Reversal, and after deletion\n",
      "--------------------\n",
      "90\n",
      "50\n",
      "60\n",
      "70\n",
      "After Reversal\n",
      "--------------------\n",
      "70\n",
      "60\n",
      "50\n",
      "90\n",
      "After Mid Deletion\n",
      "--------------------\n",
      "70\n",
      "60\n",
      "90\n",
      "List One\n",
      "--------------------\n",
      "70\n",
      "List Two\n",
      "--------------------\n",
      "90\n",
      "60\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "90"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# define a new list\n",
    "circular_list = CircularLinkedList()\n",
    "\n",
    "# insert a few values at the end\n",
    "circular_list.insert_end(50)\n",
    "circular_list.insert_end(60)\n",
    "circular_list.insert_end(70)\n",
    "\n",
    "# insert a few values at the beginning\n",
    "circular_list.insert_beg(90)\n",
    "circular_list.insert_beg(100)\n",
    "\n",
    "print('After Insertion')\n",
    "print('-'*20)\n",
    "circular_list.traverse()\n",
    "\n",
    "# grab a node\n",
    "first_node = circular_list.end\n",
    "\n",
    "# insert value inbetween two nodes.\n",
    "circular_list.insert_mid(first_node,20)\n",
    "\n",
    "print('After Mid Insertion')\n",
    "print('-'*20)\n",
    "circular_list.traverse()\n",
    "\n",
    "# delete the first and last value\n",
    "circular_list.delete_beg()\n",
    "circular_list.delete_end()\n",
    "\n",
    "print('Before Reversal, and after deletion')\n",
    "print('-'*20)\n",
    "circular_list.traverse()\n",
    "\n",
    "# reverse the list\n",
    "circular_list.reverse()\n",
    "\n",
    "print('After Reversal')\n",
    "print('-'*20)\n",
    "circular_list.traverse()\n",
    "\n",
    "# return the list size\n",
    "circular_list.list_size()\n",
    "\n",
    "# delete a node at position 3\n",
    "circular_list.delete_mid(3)\n",
    "\n",
    "print('After Mid Deletion')\n",
    "print('-'*20)\n",
    "circular_list.traverse()\n",
    "\n",
    "# grab the node before the second node\n",
    "second_node = circular_list.head.next_node\n",
    "circular_list.get_prev_node(second_node)\n",
    "\n",
    "\n",
    "# define two new lists\n",
    "head1 = CircularLinkedList()\n",
    "head2 = CircularLinkedList()\n",
    "\n",
    "circular_list.split_list_2(head1, head2)\n",
    "# # split the lists\n",
    "# circular_list.split_list(head1, head2)\n",
    "\n",
    "\n",
    "print('List One')\n",
    "print('-'*20)\n",
    "head1.traverse()\n",
    "\n",
    "print('List Two')\n",
    "print('-'*20)\n",
    "head2.traverse()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
